$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Техника два показивача

Угнежђене петље обично подразумевају постојање две бројачке променљиве од којих спољашња само увећава своју вредност током итерације, док се вредност бројачке петље у унутрашњој увећава до неке горње границе, затим се поново враћа на неку доњу границу и поново увећава и то се понавља више пута, све док спољашња бројачка променљива не достигне своју максималну вредност. Ово по правилу доводи до квадратне сложености (тј. сложености вишег степена у случају угнежђавања већег броја петљи).

Техника два показивача обухвата широку класу ефикасних алгоритама које такође карактерише постојање две или више бројачких променљивих, које се крећу кроз елементе неког низа (често сортираног). Међутим, оно што је карактеристично за њих је то што се, за разлику од унутрашњих променљивих у угнежђеним петљама, ове променљиве стално “крећу у истом смеру”, тј. вредност им се или стално повећава или стално смањује (а честа је и комбинација где се “низ обилази са два краја”, где се једна променљива стално повећава, а друга стално смањује). Техничка реализација може бити било помоћу једне петље која контролише вредности обе променљиве, било помоћу угнежђених петљи, али тако да се након завршетка тела унутрашње петље, спољашња променљива увећава до места где се унутрашња петља завршила. Пошто се свака променљива може променити највише \(n\) пута (где је \(n\) неко горње ограничење њихове вредности, обично дужина низа), број промена (па самим тим и извршавања тела петље) је највише \(2n\) и линеаран је по \(n\) тј. сложеност му је \(O(n)\).

Алгоритми засновани на техници два показивача обично могу да се изведу коришћењем одсецања примењених на угнежђене петље, па је, као и код сваке примене одсецања, потребно пажљиво образложити њихову коректност.

Техника два показивача — zadaci

Обједињавање

Za ovaj zadatak možete videti rešenje
pokušalo: 638, rešilo: 90%

Сортирани квадрати бројева

Za ovaj zadatak možete videti rešenje
pokušalo: 277, rešilo: 73%

Заједнички елементи три уређена низа

pokušalo: 561, rešilo: 72%

Близанци

pokušalo: 597, rešilo: 87%

Прости чиниоци 235

Za ovaj zadatak možete videti rešenje
pokušalo: 234, rešilo: 75%

Сегмент датог збира у низу природних бројева

Za ovaj zadatak možete videti rešenje
pokušalo: 205, rešilo: 27%

Број сегмената малог збира

pokušalo: 118, rešilo: 73%

Кајмак

pokušalo: 108, rešilo: 79%

Тастатура и миш

pokušalo: 248, rešilo: 79%

Двобојка

Za ovaj zadatak možete videti rešenje
pokušalo: 149, rešilo: 91%

Тробојка

Za ovaj zadatak možete videti rešenje
pokušalo: 102, rešilo: 91%

Оптимални сервис

pokušalo: 129, rešilo: 79%

Два блиска предајника

pokušalo: 142, rešilo: 90%

Светиљка

pokušalo: 86, rešilo: 83%

Број парова датог збира

pokušalo: 402, rešilo: 88%

Тројке датог збира (3sum)

pokušalo: 221, rešilo: 88%

Разлика висина

Za ovaj zadatak možete videti rešenje
pokušalo: 159, rešilo: 67%

Пуно фигурица

pokušalo: 282, rešilo: 69%

Пар производа у ранцу

Za ovaj zadatak možete videti rešenje
pokušalo: 61, rešilo: 73%

Број сегмената са различитим елементима

Za ovaj zadatak možete videti rešenje
pokušalo: 135, rešilo: 84%

Конференција

pokušalo: 81, rešilo: 70%

Најкраћа подниска која садржи све дате карактере

pokušalo: 175, rešilo: 82%

Квадратно-троугаони бројеви

pokušalo: 59, rešilo: 33%

Кружни пут

Za ovaj zadatak možete videti rešenje
pokušalo: 66, rešilo: 81%

Двоструко сортирана претрага

Za ovaj zadatak možete videti rešenje
pokušalo: 87, rešilo: 85%